package algorithm.leetcode.I1to100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


/**
 * 回溯题画出递归树,本题与78题不一样的是多了一个剪枝的步骤,这个也需要在图中画出来然后想清楚
 */

public class Q90 {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> lists = new LinkedList<>();
        List<Integer> curr = new LinkedList<>();
        Arrays.sort(nums);
        backtrack(lists, nums, 0, curr);
        return lists;
    }

    public void backtrack(List<List<Integer>> result,
                          int[] nums,
                          int start,
                          List<Integer> curr) {

        // 正常回溯在这里添加条件,但是本题可以由start控制起始和结束,见力扣78题,故可以不写结束条件

        // 添加当前解
        result.add(new LinkedList<>(curr));

        // 展开回溯
        for (int i = start; i < nums.length; i++) {
            // 树的某一层刚开始的时候是不跳过的,所以i>start,一开始我写成了i>0,所以漏掉了很多解
            if (i > start && nums[i] == nums[i-1]) continue;

            curr.add(nums[i]);
            backtrack(result, nums, i+1, curr);
            curr.remove(curr.size()-1);
        }

    }

    public static void main(String[] args) {
        Q90 nineZero = new Q90();
        System.out.println(nineZero.subsetsWithDup(new int[]{1, 2, 2}));
    }


}
